package com.cat.dynamicPlanning;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-cost-for-tickets/
 * @create 2025/8/26 10:34
 * @since JDK17
 */

public class Solution01 {
    static int[] duration = {1, 7, 30};
    static int[] dp = new int[366];
    int f1(int[] days, int[] costs, int cur) {
        if (cur == days.length) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0, j = cur; i < 3; i++) {
            while (j < days.length && days[cur] + duration[i] > days[j]) {
                j++;
            }
            ans = Math.min(ans, costs[i] + f1(days, costs, j));
        }
        return ans;
    }

    int f2(int[] days, int[] costs, int cur) {
        if (cur == days.length) {
            return 0;
        }
        if (dp[cur] != Integer.MAX_VALUE) {
            return dp[cur];
        }
        int ans = Integer.MAX_VALUE;

        for (int i = 0, j = cur; i < 3; i++) {
            while (j < days.length && days[cur] + duration[i] > days[j]) {
                j++;
            }
            ans = Math.min(ans, costs[i] + f2(days, costs, j));
        }
        return dp[cur] = ans;
    }
    int f3(int[] days, int[] costs, int cur) {
        dp[days.length] = 0;
        for (int i = days.length - 1; i >= 0; i--) {
            for (int k = 0, j = i; k < 3; k++) {
                while (j < days.length && days[i] + duration[k] > days[j]) {
                    j++;
                }
                dp[i] = Math.min(dp[i], costs[k] + dp[j]);
            }
        }
        return dp[0];
    }

    public int mincostTickets(int[] days, int[] costs) {
        Arrays.fill(dp,0, days.length, Integer.MAX_VALUE);
        return f3(days, costs, 0);
    }
}
